<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>每日一DP(4) CF1061C(数学+线性DP+预处理) | FZSF</title><meta name="keywords" content="动态规划"><meta name="author" content="FZSF"><meta name="copyright" content="FZSF"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="题目题目描述 You are given an integer array $a_1$,$a_2$,…,$a_n$. The array bb is called to be a subsequence of $a$ if it is possible to remove some elements from $a$ to get $b$. Array $b_1$,$b_2$,…,$b_k$is">
<meta property="og:type" content="article">
<meta property="og:title" content="每日一DP(4) CF1061C(数学+线性DP+预处理)">
<meta property="og:url" content="https://fanzsfu.gitee.io/2021/11/16/%E6%AF%8F%E6%97%A5%E4%B8%80DP-4-CF1061C-%E6%95%B0%E5%AD%A6-%E7%BA%BF%E6%80%A7DP-%E9%A2%84%E5%A4%84%E7%90%86/index.html">
<meta property="og:site_name" content="FZSF">
<meta property="og:description" content="题目题目描述 You are given an integer array $a_1$,$a_2$,…,$a_n$. The array bb is called to be a subsequence of $a$ if it is possible to remove some elements from $a$ to get $b$. Array $b_1$,$b_2$,…,$b_k$is">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://pic.imgdb.cn/item/6193c6152ab3f51d91b888ad.jpg">
<meta property="article:published_time" content="2021-11-16T14:52:56.000Z">
<meta property="article:modified_time" content="2021-11-16T15:48:25.169Z">
<meta property="article:author" content="FZSF">
<meta property="article:tag" content="动态规划">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://pic.imgdb.cn/item/6193c6152ab3f51d91b888ad.jpg"><link rel="shortcut icon" href="/img/tou.png"><link rel="canonical" href="https://fanzsfu.gitee.io/2021/11/16/%E6%AF%8F%E6%97%A5%E4%B8%80DP-4-CF1061C-%E6%95%B0%E5%AD%A6-%E7%BA%BF%E6%80%A7DP-%E9%A2%84%E5%A4%84%E7%90%86/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: undefined,
  translate: undefined,
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
    },
    fancybox: {
      js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
      css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isanchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '每日一DP(4) CF1061C(数学+线性DP+预处理)',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2021-11-16 23:48:25'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const detectApple = () => {
      if (GLOBAL_CONFIG_SITE.isHome && /iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    })(window)</script><meta name="generator" content="Hexo 5.4.0"></head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://pic.imgdb.cn/item/6118dff15132923bf87690a5.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/archives/"><div class="headline">文章</div><div class="length-num">20</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/tags/"><div class="headline">标签</div><div class="length-num">5</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 清单</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://pic.imgdb.cn/item/6193c6152ab3f51d91b888ad.jpg')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">FZSF</a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 清单</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">每日一DP(4) CF1061C(数学+线性DP+预处理)</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2021-11-16T14:52:56.000Z" title="发表于 2021-11-16 22:52:56">2021-11-16</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2021-11-16T15:48:25.169Z" title="更新于 2021-11-16 23:48:25">2021-11-16</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E6%AF%8F%E6%97%A5%E4%B8%80%E9%A2%98/">每日一题</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">766</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>3分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="每日一DP(4) CF1061C(数学+线性DP+预处理)"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h2 id="题目"><a href="#题目" class="headerlink" title="题目"></a>题目</h2><p><strong>题目描述</strong></p>
<p>You are given an integer array $a_1$,$a_2$,…,$a_n$.</p>
<p>The array bb is called to be a <em>subsequence</em> of $a$ if it is possible to remove some elements from $a$ to get $b$.</p>
<p>Array $b_1$,$b_2$,…,$b_k$is called to be <em>good</em> if it is not empty and for every $i$($1\leq i\leq k$) $b_i$ is divisible by $i$.</p>
<p>Find the number of good subsequences in $a$ modulo $10^9$+$7$.</p>
<p>Two subsequences are considered different if index sets of numbers included in them are different. That is, the values of the elements do not matter in the comparison of subsequences. In particular, the array $a$ has exactly $2^n$−$1$ different subsequences (excluding an empty subsequence).</p>
<p><strong>输入描述</strong></p>
<p>The first line contains an integer $n$($1\leq n\leq 100000$) — the length of the array $a$.</p>
<p>The next line contains integers $a_1$,$a_2$,…,$a_n$($1\leq a_i\leq 10^6$).</p>
<p><strong>输出描述</strong></p>
<p>Print exactly one integer — the number of good subsequences taken modulo $10^9$+$7$.</p>
<p><strong>Examples</strong></p>
<p><strong>input</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">2</span><br><span class="line">1 2</span><br></pre></td></tr></table></figure>
<p><strong>output</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">3</span><br></pre></td></tr></table></figure>
<p><strong>input</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">5</span><br><span class="line">2 2 1 22 14</span><br></pre></td></tr></table></figure>
<p><strong>output</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">13</span><br></pre></td></tr></table></figure>
<h4 id="大体题意"><a href="#大体题意" class="headerlink" title="大体题意"></a>大体题意</h4><p>有数列$a$，他的一个子序列$b_1$,$b_2$,…,$b_k$如果满足对于所有的$b_i$都可以被$i$整除，就是一个good。</p>
<p>求对于$a$，有多少good。</p>
<h4 id="思路"><a href="#思路" class="headerlink" title="思路"></a>思路</h4><p>这道题其实想了比较久，但是一直在想直接用一维的数组来表示状态，因为开了二维会MLE，但是当推出DP方程之后是可以用滚动数组优化的。</p>
<p>所有杨哥还是说的没错的，先别管MLE还是TLE，把DP方程成功写出来再考虑优化。</p>
<p>我们可以用$dp[i] [j]$来表示遍历到第$i$个元素时，字串长度为$j$时的好数列的个数。</p>
<p>所有我们可以很容易的写出DP方程：</p>
<script type="math/tex; mode=display">
dp[i][j]= \begin{cases}dp[i-1][j]+dp[i-1][j-1],& \text {a[i]%j=0} \\ dp[i-1][j],& \text {others} \end{cases}</script><p>很明显，这样会内存超限，由于当前这一项的取值只与它的前一项有关，我们可以考虑滚动数组或者直接降成一维。</p>
<p>我这里采用将成一维的做法。</p>
<p>不过要注意，我们为了保证我们本项的值不会对结果造成贡献，应该从后向前遍历。</p>
<p>这里我们解决了MLE的问题，随之而来的却是TLE的问题。</p>
<p>但是很快我们就可以发现，只有$a_i$的因子会被更新，其他的则不会被更新，所有我们只需要每次预处理出因子即可。</p>
<p><strong>AC代码</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">1e5</span>+<span class="number">10</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> mod=<span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line">LL dp[N];</span><br><span class="line">vector&lt;<span class="keyword">int</span>&gt; v[N];</span><br><span class="line"><span class="keyword">int</span> a[N];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n;</span><br><span class="line">	<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++) <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;a[i]);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j&lt;=<span class="built_in">sqrt</span>(a[i]);j++)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="keyword">if</span>(a[i]%j==<span class="number">0</span>)</span><br><span class="line">			&#123;</span><br><span class="line">				v[i].<span class="built_in">push_back</span>(j);</span><br><span class="line">				<span class="keyword">if</span>(a[i]/j&lt;=n &amp;&amp; a[i]/j!=j) v[i].<span class="built_in">push_back</span>(a[i]/j);</span><br><span class="line">			&#125; </span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	dp[<span class="number">0</span>]=<span class="number">1</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n;i++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> j=(<span class="keyword">int</span>)v[i].<span class="built_in">size</span>()<span class="number">-1</span>;j&gt;=<span class="number">0</span>;j--)</span><br><span class="line">		&#123;</span><br><span class="line">			dp[v[i][j]]=(dp[v[i][j]]+dp[v[i][j]<span class="number">-1</span>])%mod;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	LL ans=<span class="number">0LL</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++) ans=(ans+dp[i])%mod;</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;%lld\n&quot;</span>,ans);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>提交记录：<a target="_blank" rel="noopener" href="https://codeforces.com/contest/1061/submission/135875523">Submission #135875523 - Codeforces</a></p>
<p>原题链接：<a target="_blank" rel="noopener" href="https://codeforces.com/contest/1061/problem/C">Problem - C - Codeforces</a></p>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">FZSF</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://fanzsfu.gitee.io/2021/11/16/%E6%AF%8F%E6%97%A5%E4%B8%80DP-4-CF1061C-%E6%95%B0%E5%AD%A6-%E7%BA%BF%E6%80%A7DP-%E9%A2%84%E5%A4%84%E7%90%86/">https://fanzsfu.gitee.io/2021/11/16/%E6%AF%8F%E6%97%A5%E4%B8%80DP-4-CF1061C-%E6%95%B0%E5%AD%A6-%E7%BA%BF%E6%80%A7DP-%E9%A2%84%E5%A4%84%E7%90%86/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://fanzsfu.gitee.io" target="_blank">FZSF</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a></div><div class="post_share"><div class="social-share" data-image="https://pic.imgdb.cn/item/6193c6152ab3f51d91b888ad.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2022/01/11/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-7-%E2%80%94%E2%80%94%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/"><img class="prev-cover" src="https://pic.imgdb.cn/item/61dd7c6b2ab3f51d91b9e054.png" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">算法学习笔记(7)——树状数组</div></div></a></div><div class="next-post pull-right"><a href="/2021/11/15/%E6%AF%8F%E6%97%A5%E4%B8%80DP-3-CF455A-%E7%BA%BF%E6%80%A7DP/"><img class="next-cover" src="https://pic.imgdb.cn/item/6191f6022ab3f51d9115e383.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">每日一DP(3) CF455A (线性DP)</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span> 相关推荐</span></div><div class="relatedPosts-list"><div><a href="/2021/11/12/每日一DP-1-CF946D-分组背包-预处理/" title="每日一DP(1) CF946D (分组背包+预处理)"><img class="cover" src="https://pic.imgdb.cn/item/60a9dd7f35c5199ba7dded6b.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-11-12</div><div class="title">每日一DP(1) CF946D (分组背包+预处理)</div></div></a></div><div><a href="/2021/11/15/每日一DP-3-CF455A-线性DP/" title="每日一DP(3) CF455A (线性DP)"><img class="cover" src="https://pic.imgdb.cn/item/6191f6022ab3f51d9115e383.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-11-15</div><div class="title">每日一DP(3) CF455A (线性DP)</div></div></a></div><div><a href="/2021/11/13/每日一DP-2-CF191A-线性DP/" title="每日一DP(2) CF191A (线性DP)"><img class="cover" src="https://pic.imgdb.cn/item/618f6bec2ab3f51d914eee77.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-11-13</div><div class="title">每日一DP(2) CF191A (线性DP)</div></div></a></div><div><a href="/2022/01/13/每日一DP-5-CF1625C-线性DP/" title="每日一DP(5) CF1625C (线性DP)"><img class="cover" src="https://pic.imgdb.cn/item/61dffe022ab3f51d91788e88.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-01-13</div><div class="title">每日一DP(5) CF1625C (线性DP)</div></div></a></div><div><a href="/2022/03/21/每日一DP-6-Leetcode-2172-状压DP/" title="每日一DP(6) Leetcode 2172(状压DP)"><img class="cover" src="https://pic.imgdb.cn/item/6237ef7527f86abb2af1c508.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-03-21</div><div class="title">每日一DP(6) Leetcode 2172(状压DP)</div></div></a></div><div><a href="/2021/08/23/算法学习笔记-2——树型DP/" title="算法学习笔记(2)——树型DP"><img class="cover" src="https://pic.imgdb.cn/item/6123b76844eaada739b8cba7.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-08-23</div><div class="title">算法学习笔记(2)——树型DP</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://pic.imgdb.cn/item/6118dff15132923bf87690a5.jpg" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">FZSF</div><div class="author-info__description">记录与成长</div></div><div class="card-info-data"><div class="card-info-data-item is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">20</div></a></div><div class="card-info-data-item is-center"><a href="/tags/"><div class="headline">标签</div><div class="length-num">5</div></a></div><div class="card-info-data-item is-center"><a href="/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div></div><a class="button--animated" id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/Elbow-Leaf"><i class="fab fa-github"></i><span>Follow Me</span></a></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>公告</span></div><div class="announcement_content">This is my Blog</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%A2%98%E7%9B%AE"><span class="toc-number">1.</span> <span class="toc-text">题目</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%A4%A7%E4%BD%93%E9%A2%98%E6%84%8F"><span class="toc-number">1.0.1.</span> <span class="toc-text">大体题意</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF"><span class="toc-number">1.0.2.</span> <span class="toc-text">思路</span></a></li></ol></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/2022/06/04/2022%E5%B9%B4%E5%B1%B1%E4%B8%9C%E7%9C%81ICPC%E7%9C%81%E8%B5%9B%E6%B8%B8%E8%AE%B0/" title="2022年山东省ICPC省赛游记"><img src="https://pic.imgdb.cn/item/629b123b09475431292426f7.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="2022年山东省ICPC省赛游记"/></a><div class="content"><a class="title" href="/2022/06/04/2022%E5%B9%B4%E5%B1%B1%E4%B8%9C%E7%9C%81ICPC%E7%9C%81%E8%B5%9B%E6%B8%B8%E8%AE%B0/" title="2022年山东省ICPC省赛游记">2022年山东省ICPC省赛游记</a><time datetime="2022-06-04T07:59:36.000Z" title="发表于 2022-06-04 15:59:36">2022-06-04</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/04/11/%E5%B1%B1%E4%B8%9C%E5%A4%9A%E6%A0%A1%E9%9B%86%E8%AE%AD1%E6%80%BB%E7%BB%93%EF%BC%88%E6%B5%81%E6%B0%B4%E8%B4%A6%EF%BC%89%E9%99%84%E4%B8%8D%E5%AE%8C%E5%85%A8%E9%A2%98%E8%A7%A3/" title="山东多校集训1总结（流水账）附不完全题解"><img src="https://pic.imgdb.cn/item/6253b949239250f7c54a1415.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="山东多校集训1总结（流水账）附不完全题解"/></a><div class="content"><a class="title" href="/2022/04/11/%E5%B1%B1%E4%B8%9C%E5%A4%9A%E6%A0%A1%E9%9B%86%E8%AE%AD1%E6%80%BB%E7%BB%93%EF%BC%88%E6%B5%81%E6%B0%B4%E8%B4%A6%EF%BC%89%E9%99%84%E4%B8%8D%E5%AE%8C%E5%85%A8%E9%A2%98%E8%A7%A3/" title="山东多校集训1总结（流水账）附不完全题解">山东多校集训1总结（流水账）附不完全题解</a><time datetime="2022-04-11T04:18:00.000Z" title="发表于 2022-04-11 12:18:00">2022-04-11</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/03/21/%E6%AF%8F%E6%97%A5%E4%B8%80DP-6-Leetcode-2172-%E7%8A%B6%E5%8E%8BDP/" title="每日一DP(6) Leetcode 2172(状压DP)"><img src="https://pic.imgdb.cn/item/6237ef7527f86abb2af1c508.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="每日一DP(6) Leetcode 2172(状压DP)"/></a><div class="content"><a class="title" href="/2022/03/21/%E6%AF%8F%E6%97%A5%E4%B8%80DP-6-Leetcode-2172-%E7%8A%B6%E5%8E%8BDP/" title="每日一DP(6) Leetcode 2172(状压DP)">每日一DP(6) Leetcode 2172(状压DP)</a><time datetime="2022-03-21T02:40:26.000Z" title="发表于 2022-03-21 10:40:26">2022-03-21</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/03/18/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-8-%E2%80%94%E2%80%94%E8%83%8C%E5%8C%85DP/" title="算法学习笔记(8)——背包DP"><img src="https://pic.imgdb.cn/item/623403185baa1a80abe33090.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="算法学习笔记(8)——背包DP"/></a><div class="content"><a class="title" href="/2022/03/18/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0-8-%E2%80%94%E2%80%94%E8%83%8C%E5%8C%85DP/" title="算法学习笔记(8)——背包DP">算法学习笔记(8)——背包DP</a><time datetime="2022-03-18T00:58:52.000Z" title="发表于 2022-03-18 08:58:52">2022-03-18</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/01/13/%E6%AF%8F%E6%97%A5%E4%B8%80DP-5-CF1625C-%E7%BA%BF%E6%80%A7DP/" title="每日一DP(5) CF1625C (线性DP)"><img src="https://pic.imgdb.cn/item/61dffe022ab3f51d91788e88.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="每日一DP(5) CF1625C (线性DP)"/></a><div class="content"><a class="title" href="/2022/01/13/%E6%AF%8F%E6%97%A5%E4%B8%80DP-5-CF1625C-%E7%BA%BF%E6%80%A7DP/" title="每日一DP(5) CF1625C (线性DP)">每日一DP(5) CF1625C (线性DP)</a><time datetime="2022-01-13T10:03:53.000Z" title="发表于 2022-01-13 18:03:53">2022-01-13</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2021 - 2022 By FZSF</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><div class="js-pjax"><script>if (!window.MathJax) {
  window.MathJax = {
    tex: {
      inlineMath: [ ['$','$'], ["\\(","\\)"]],
      tags: 'ams'
    },
    chtml: {
      scale: 1.2
    },
    options: {
      renderActions: {
        findScript: [10, doc => {
          for (const node of document.querySelectorAll('script[type^="math/tex"]')) {
            const display = !!node.type.match(/; *mode=display/)
            const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display)
            const text = document.createTextNode('')
            node.parentNode.replaceChild(text, node)
            math.start = {node: text, delim: '', n: 0}
            math.end = {node: text, delim: '', n: 0}
            doc.math.push(math)
          }
        }, ''],
        insertScript: [200, () => {
          document.querySelectorAll('mjx-container:not\([display]\)').forEach(node => {
            const target = node.parentNode
            if (target.nodeName.toLowerCase() === 'li') {
              target.parentNode.classList.add('has-jax')
            } else {
              target.classList.add('has-jax')
            }
          });
        }, '', false]
      }
    }
  }
  
  const script = document.createElement('script')
  script.src = 'https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js'
  script.id = 'MathJax-script'
  script.async = true
  document.head.appendChild(script)
} else {
  MathJax.startup.document.state(0)
  MathJax.texReset()
  MathJax.typeset()
}</script></div><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>